The popularity of voice and video applications over mobile computing devices has raised concerns regarding the performance of medium access control (MAC) protocols, which are responsible for allocating shared medium resources to multiple communicating stations and resolving collisions that occur when two or more stations access the medium simultaneously. In the current IEEE 802.11 wireless LANs, the distributed coordination function (DCF) of the MAC protocol layer uses a binary exponential back-off (BEB) algorithm for fundamental channel access. The BEB algorithm mitigates the issue of network collisions by randomizing the timing of medium access among stations that share the communication medium. However, as demonstrated by both practical experience and theoretical analysis, the BEB algorithm has some deficiencies. First, the collision probability for a transmission attempt increases exponentially with the number of active stations in the network, which significantly impairs the network throughput for large-scale networks. Second, the medium access delay cannot be bounded and the jitter is variable, which may not be suitable for multimedia applications. Third, the opportunity for medium access is not fair among stations. That is, a given station may gain access to the communication medium and get served for a long time. This results in other stations having to greatly defer their access to the medium. Moreover, it turns out that the use of doubling the contention window upon failed transmissions appears to give more transmission opportunities to these successful stations.
The concept of reducing or eliminating contention in contention-based networks was introduced by the present Applicants using a form of round robin scheduling in an earlier patent applications PCT Application Ser. Nos. PCT/US2007/014607 and PCT/US2007/014608. This concept works well in contention-based networks where there is a centralized controller or coordinator, which can be the global repository of knowledge and equally importantly disseminate and distribute that global knowledge in order to coordinate the activities of the nodes or stations of the network.
The earlier applications described a back-off method that sought to improve the performance of the legacy random back-off procedure. The method adopted a different approach to resolve external collisions. Deterministic values were selected for the back-off slot counts. Thus, there was no duplication among distributed slot counts and each station could exclusively access the medium without colliding with others. By cycling the slot count though a fixed interval [0, N], where N was the number of stations in the network, the method offered a round robin type service among the stations. Therefore, the method provided guaranteed fairness for the network, and furthermore analysis showed that the method had high network efficiency for moderate to heavy traffic loads. The round robin type service cycling through the N stations amounted to scheduling stations such that each station received a fair amount of time. The stations could be mobile or fixed and the network could be wired or wireless. However, the station might also have been stationary and the network could have been any contention-based network. That invention was directed to any contention-based network where the station used a physical or virtual carrier sense mechanism to determine if the network was busy. This included any networks whose MAC layer protocol builds on CSMA, such as cable networks. Note that the term “slot” in the following text may refer to a period of uninterrupted frame exchange (a busy time slot), or a fixed duration for physical carrier sensing (an idle time slot).
A major feature of the method was that, under saturated traffic scenarios, the time interval/period between successive frame exchange sequences initiated by two separate stations was only one Distributed coordination function Inter-Frame Slot (DIFS) plus one slot time. Such an inter-space time interval/period was shorter than that of conventional random back-off methods used by DCF/EDCA (Enhanced Distributed Channel Access), but longer than the Point Coordination Function (PCF) time interval/period that is used by the PCF/HCCA (Hybrid coordination function (HCF) Controlled Channel Access) mechanism. Moreover, the method regulated a sequential service order among the stations, while conventional random back-off methods did not have such a feature. As used herein, “/” denotes alternative names for the same or similar components or structures. That is, a “/” can be taken as meaning “or” as used herein.
Network collisions are an annoying issue for the CSMA based wireless communications, as collisions greatly degenerate network performance, particularly in terms of throughput and network efficiency. However, collisions are eliminated (or greatly reduced) in the deterministic back-off (communication medium access) method of Applicants' earlier applications. Each station could exclusively take control of the communication medium after its slot count reached zero. In this sense, the deterministic back-off method outperformed legacy random back-off methods. An alternative embodiment included an option of inserting a station/node into the round robin service schedule more than once per round. This alternative embodiment permitted a form of prioritization.
FIG. 2 depicts the time slot assignments of Applicants' earlier applications. A mobile station i running the deterministic back-off method decrements its slot count slot(i) whenever the medium has been sensed to be idle for a DIFS time. It should be noted that the number of slots is in general equal to the number of station/nodes. In the alternative embodiment where a form of prioritization was described, the slot count was greater than the number of stations/nodes to accommodate insertion of a given station/node more than once in the schedule of round robin service. When the slot count slot(i) reaches zero and there is a frame pending in the transmission queue, station/node commences frame transmission. The slot count determined when the mobile station needed to restart the slot counter for a new round of service was calculated deterministically using the deterministic back-off method using the following two equations:slot(i)=C0(i,t,{right arrow over (x)})  (1)slot(i)=C1(i,t,{right arrow over (x)})  (2)where i is the station ID, t is the current time and {right arrow over (x)} is the state variable vector that represents information necessary for the decision. The first equation is used for a station to access the network for the first time after successful association with the network. The second equation is used in subsequent iterations. Both C0(i, t, x) and C1(i, t, x) are deterministic functions that given the value of i, t and {right arrow over (x)}, a unique value for each station is derived as the output. Thus, at this step, instead of selecting the slot count slot(i) randomly within a contention window as in the BEB algorithm, the slot count is reset to a deterministic value according to equations (1) and (2).
FIG. 1 is a flowchart of the operation of the deterministic back-off method of Applicants' earlier applications from the perspective of the station. At 160 the joining station sends a request to join the network to the AP. The joining station then waits until it receives the communications medium access (deterministic back-off) method from the AP, as well as the slot count, the number of stations in the network and the address queue at 165. At 170, the joining station determines if it supports the communication medium access (deterministic back-off) method used by the network. If the joining station determines that it supports the communication medium access method then it saves the slot count, the address queue and the number of stations in the network at 180. The station proceeds as described above to gain access to the communication medium in accordance with the principles of the invention. If the joining station determines that is does not support the communication medium access method of the invention then it sends the AP a dissociation message at 175. Of course, if the joining station is already a member of (associated with) the network then 160, 165, 170, 175 and 180 are skipped/not executed. If the joining station is already associated with the network then the AP waits a predetermined time period at 150. The slot count is adjusted at 125. In an exemplary embodiment the slot count is decremented by one. An adjustment that is incremented could also be used. The slot count is compared to a predetermined value at 130. The exemplary embodiment of FIG. 1 compares the adjusted (decremented) slot count to 0. If the slot count has reached the predetermined value then at 135 the station determines if the station has a data frame to transmit. If the station has a data frame to transmit then data frame transmission is initiated at 140. If the station does not have a data frame to transmit then the station skips its turn and selects a new slot count at 145. Once data frame transmission has been initiated then the station selects a new slot count at 145. If the slot count had not reached the predetermined value at 130, then the station waits a predetermined time period at 150.
In the deterministic back-off method of the earlier applications, a new round of back-off was invoked whenever the slot count was decremented to zero, regardless of the status of pending transmission queue. When the slot count reached zero but there was no data to send, the station would forgo its transmission opportunity and go to the next round of back-off by re-setting the slot count according to equation (2). This mechanism was introduced to preserve the relationship between the distributed slot counts during the network's operation.
Functions C0(i, t, {right arrow over (x)}) and C1(i, t, {right arrow over (x)}) were carefully designed to derive appropriate values when setting the slot count. In that design, at any time, all the slot count values in the network formed a set whose cardinality was equal to (or greater than if prioritization is offered) the number of stations. Considering the efficiency of the algorithm in terms of network utility, the maximum element of the set S (denoted as max(S)) was set to a value as small as possible. A small max(S) means a shorter time between successive service opportunities for a station/node. A large max(S) may waste bandwidth because some time slots would never be used by any station/node. In one embodiment, both functions were chosen as constant functions with the constant being the number of stations/nodes associated with the network. That is,C0(i,t,{right arrow over (x)})=N  (3)C1(i,t,{right arrow over (x)})=N  (4)
The deterministic back-off method based on equations (3) and (4) formed a round robin service among stations. FIG. 2 gives an exemplary illustration of the first embodiment. In view of the shared network medium, each time slot is assigned to a specific station. The time slot served as the entry for that station to access the medium. A medium access opportunity is granted to a station whenever its slot count was decremented to zero. Thus, the transmission opportunity is passed around the stations/nodes in a round robin manner. During each round of service, a station/node is granted exactly one opportunity for data transmission. If at that time it has no pending data in its transmission buffer, it forgoes the transmission opportunity, and another station with next higher slot count takes over the opportunity in the next time slot.
In an alternative embodiment, however, while max(s) was set as small as possible, max(s) may be greater than the number of stations/nodes in order to permit insertion of a given node(s)/station(s) into the round of service more than once and thereby provide a form of prioritization.
However, the above method does not work well in an infrastructureless network, such as a peer-to-peer network, where there is no central coordinator or controller to be the global repository and to disseminate such knowledge in order to coordinate the nodes and stations. Peer-to-peer networks are further complicated because nodes and stations in a peer-to-peer network may join or leave the network at any time. Further performance degrades using the DEB method in cases where the number of active station is small and/or the traffic load is light.